//
// Created by 高森森 on 2022/2/10.
//

#ifndef LEETCODE_SOLUTION33_H
#define LEETCODE_SOLUTION33_H
#include<iostream>
#include<vector>
#include <string.h>
#include <numeric>

using namespace std;

class Solution33 {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        int fa[n+1],rank[n+1];
        iota(fa,fa+n+1,0);
        for(int i=1;i<n+1;i++){
            rank[i]=1;
        }
        for(int i=threshold+1;i<=n;i++)
            for(int j=2*i;j<=n;j+=i){
                merge(i,j,fa,rank);
            }
        vector<bool>ans;
        for(auto q:queries){
            if(find(q[0],fa)==find(q[1],fa)){
                ans.push_back(1);
            }else{
                ans.push_back(0);
            }

        }
        return ans;

    }
    //并查集
    //查找根节点
    int find(int x,int *fa){
        if(x==fa[x])
            return x;
        else{
            fa[x]=find(fa[x],fa);//将沿途所有节点的父结点都设置为根节点
            return fa[x];
        }
    }
    //按秩合并
    void merge(int i,int j,int*fa,int*rank){
        int x=find(i,fa);
        int y=find(j,fa);
        if(rank[x]<=rank[y])
        {
            fa[x]=y;
        }else{
            fa[y]=x;
        }
        if(rank[x]==rank[y]&&x!=y){
            rank[y]++;
        }
    }
};


#endif //LEETCODE_SOLUTION33_H
